SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Constant-weight code</title>

</head>

Constant-weight code

</h1>

</header>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, a constant-weight code, also called an m-of-n code or m-out-of-n code, is an <a href="Error_detection_and_correction" title="Error detection and correction">error detection and correction</a> code where all codewords share the same <a href="Hamming_weight" title="Hamming weight">Hamming weight</a>.

The <a href="One-hot" title="One-hot">one-hot</a> code and the balanced code are two widely used kinds of constant-weight code.

The theory is closely connected to that of <a href="Combinatorial_design" title="Combinatorial design">designs</a> (such as <a href="Block_design" title="Block design">t-designs</a> and <a href="Steiner_system" title="Steiner system">Steiner systems</a>). Most of the work on this field of <a href="Discrete_mathematics" title="Discrete mathematics">discrete mathematics</a> is concerned with binary constant-weight codes.

Binary constant-weight codes have several applications, including <a href="Frequency-hopping_spread_spectrum" title="Frequency-hopping spread spectrum">frequency hopping</a> in <a href="Global_System_for_Mobile_Communications" class="mw-redirect" title="Global System for Mobile Communications">GSM</a> networks.<a href="#cite_note-smith-1">[1]</a>

Most <a href="Barcode" title="Barcode">barcodes</a> use a binary constant-weight code to simplify automatically setting the brightness threshold that distinguishes black and white stripes.

Most <a href="Line_code" title="Line code">line codes</a> use either a constant-weight code, or a nearly-constant-weight <a href="Paired_disparity_code" title="Paired disparity code">paired disparity code</a>.

In addition to use as error correction codes, the large space between code words can also be used in the design of <a href="Asynchronous_circuit" title="Asynchronous circuit">asynchronous circuits</a> such as <a href="Delay_insensitive_circuit" title="Delay insensitive circuit">delay insensitive circuits</a>.

Constant-weight codes, like <a href="Berger_code" title="Berger code">Berger codes</a>, can detect all unidirectional errors.

The central problem regarding constant-weight codes is the following: what is the maximum number of codewords in a binary constant-weight code with length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">, and weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">? This number is called <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(n,d,w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(n,d,w)}</annotation>

</semantics>

</math><img src="./156dbc9f3cfec48cf025dc737af3f8ba89cc795c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.895ex; height:2.843ex;" alt="{\displaystyle A(n,d,w)}" loading="lazy">.

Apart from some trivial observations, it is generally impossible to compute these numbers in a straightforward way. Upper bounds are given by several important theorems such as the <a href="First_Johnson_bound" class="mw-redirect" title="First Johnson bound">first</a> and <a href="Second_Johnson_bound" class="mw-redirect" title="Second Johnson bound">second Johnson bounds</a>,<a href="#cite_note-2">[2]</a> and better upper bounds can sometimes be found in other ways. Lower bounds are most often found by exhibiting specific codes, either with use of a variety of methods from discrete mathematics, or through heavy computer searching. A large table of such record-breaking codes was published in 1990,<a href="#cite_note-brouwer-3">[3]</a> and an extension to longer codes (but only for those values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> which are relevant for the GSM application) was published in 2006.<a href="#cite_note-smith-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="1-of-N_codes">1-of-N codes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="One-hot" title="One-hot">one-hot</a></div>

A special case of constant weight codes are the one-of-N codes, that encode <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}N}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}N}</annotation>

</semantics>

</math><img src="./ebbb0de63b56848f6d121470d64eb2359472a6e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.477ex; height:2.676ex;" alt="{\displaystyle \log _{2}N}" loading="lazy"> bits in a code-word of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> bits. The one-of-two code uses the code words 01 and 10 to encode the bits '0' and '1'. A one-of-four code can use the words 0001, 0010, 0100, 1000 in order to encode two bits 00, 01, 10, and 11. An example is dual rail encoding, and chain link <a href="#cite_note-4">[4]</a> used in delay insensitive circuits. For these codes, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=N,~d=2,~w=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=N,~d=2,~w=1}</annotation>

</semantics>

</math><img src="./ebfcfdcbda0cb5a73f60b21a3d1dae71b03152e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.188ex; height:2.509ex;" alt="{\displaystyle n=N,~d=2,~w=1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(n,d,w)=n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(n,d,w)=n}</annotation>

</semantics>

</math><img src="./89194d795169c68c89694a64768c1b1955d01dce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.388ex; height:2.843ex;" alt="{\displaystyle A(n,d,w)=n}" loading="lazy">.

Some of the more notable uses of one-hot codes include

<a href="Biphase_mark_code" class="mw-redirect" title="Biphase mark code">biphase mark code</a> uses a 1-of-2 code;

<a href="Pulse-position_modulation" title="Pulse-position modulation">pulse-position modulation</a> uses a 1-of-n code;

<a href="Address_decoder" title="Address decoder">address decoder</a>,

etc.

<div class="mw-heading mw-heading2"><h2 id="Balanced_code">Balanced code</h2></div>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, a balanced code is a <a href="Binary_numeral_system" class="mw-redirect" title="Binary numeral system">binary</a> <a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">forward error correction</a> code for which each codeword contains an equal number of zero and one bits. Balanced codes have been introduced by <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>;<a href="#cite_note-knuth-5">[5]</a> they are a subset of so-called unordered codes, which are codes having the property that the positions of ones in a codeword are never a subset of the positions of the ones in another codeword. Like all unordered codes, balanced codes are suitable for the detection of all <a href="Unidirectional_error" class="mw-redirect" title="Unidirectional error">unidirectional errors</a> in an encoded message. Balanced codes allow for particularly efficient decoding, which can be carried out in parallel.<a href="#cite_note-knuth-5">[5]</a><a href="#cite_note-optimal-6">[6]</a><a href="#cite_note-7">[7]</a>

Some of the more notable uses of balanced-weight codes include

<a href="Biphase_mark_code" class="mw-redirect" title="Biphase mark code">biphase mark code</a> uses a 1 of 2 code;

<a href="6b/8b_encoding" title="6b/8b encoding">6b/8b encoding</a> uses a 4 of 8 code;

the <a href="Hadamard_code" title="Hadamard code">Hadamard code</a> is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k-1}}</annotation>

</semantics>

</math><img src="./ddfa44836396d742f76f25213117e820c4584d2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.352ex; height:2.676ex;" alt="{\displaystyle 2^{k-1}}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>

</semantics>

</math><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy"> code (except for the zero codeword),

the <a href="IEEE_1355#Slice:_TS-FO-02" title="IEEE 1355">three-of-six</a> code;

etc.

The 3-wire lane encoding used in <a href="MIPI_Alliance" title="MIPI Alliance"> MIPI</a> C-PHY can be considered a generalization of constant-weight code to ternary -- each wire transmits a <a href="Ternary_signal" title="Ternary signal">ternary signal</a>, and at any one instant one of the 3 wires is transmitting a low, one is transmitting a middle, and one is transmitting a high signal.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="m-of-n_codes">m-of-n codes</h2></div>

An m-of-n code is a separable <a href="Error_detection" class="mw-redirect" title="Error detection">error detection</a> code with a code word length of n bits, where each code word contains exactly m instances of a "one". A single bit error will cause the code word to have either m + 1 or m − 1 "ones". An example m-of-n code is the <a href="Two-out-of-five_code" title="Two-out-of-five code">2-of-5 code</a> used by the <a href="United_States_Postal_Service" title="United States Postal Service">United States Postal Service</a>.

The simplest implementation is to append a string of ones to the original data until it contains m ones, then append zeros to create a code of length n.

Example:

<caption>3-of-6 code

</caption>

<th>Original 3 data bits</th>

<th>Appended bits

</th></tr>

<tr>

<td>111

</td></tr>

<tr>

<td>110

</td></tr>

<tr>

<td>110

</td></tr>

<tr>

<td>100

</td></tr>

<tr>

<td>110

</td></tr>

<tr>

<td>100

</td></tr>

<tr>

<td>100

</td></tr>

<tr>

<td>000

</td></tr>

</tbody></table>

Some of the more notable uses of constant-weight codes, other than the one-hot and balanced-weight codes already mentioned above, include

<a href="Code_39" title="Code 39">Code 39</a> uses a 3-of-9 code;

<a href="Bi-quinary_coded_decimal" title="Bi-quinary coded decimal">bi-quinary coded decimal</a> code uses a 2-of-7 code,

the <a href="Two-out-of-five_code" title="Two-out-of-five code">2-of-5 code</a>,

etc.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-smith-1">^ <a href="#cite_ref-smith_1-0">a</a> <a href="#cite_ref-smith_1-1">b</a> D. H. Smith, L. A. Hughes and S. Perkins (2006). "<a rel="nofollow" class="external text" href="http://www.combinatorics.org/Volume_13/Abstracts/v13i1a2.html">A New Table of Constant Weight Codes of Length Greater than 28</a>". The Electronic Journal of Combinatorics 13.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> See pp. 526–527 of F. J. MacWilliams and N. J. A. Sloane (1979). The Theory of Error-Correcting Codes. Amsterdam: North-Holland.

</li>

<li id="cite_note-brouwer-3"><a href="#cite_ref-brouwer_3-0">^</a> A. E. Brouwer, James B. Shearer, N. J. A. Sloane and Warren D. Smith (1990). "A New Table of Constant Weight Codes". IEEE Transactions of Information Theory 36.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFW.J._BainbridgeA._BardsleyR.W._McGuffin" class="citation news cs1">W.J. Bainbridge; A. Bardsley; R.W. McGuffin. <a rel="nofollow" class="external text" href="http://www.design-reuse.com/articles/14561/system-on-chip-design-using-self-timed-networks-on-chip.html">"System-on-Chip Design using Self-timed Networks-on-Chip"</a>.</cite>

</li>

<li id="cite_note-knuth-5">^ <a href="#cite_ref-knuth_5-0">a</a> <a href="#cite_ref-knuth_5-1">b</a> <cite id="CITEREFD.E._Knuth1986" class="citation journal cs1">D.E. Knuth (January 1986). <a rel="nofollow" class="external text" href="http://www.costasarrays.org/costasrefs/knuth86efficient.pdf">"Efficient balanced codes"</a> (PDF). IEEE Transactions on Information Theory. 32 (1): 51–53. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1986.1057136">10.1109/TIT.1986.1057136</a>.</cite>

</li>

<li id="cite_note-optimal-6"><a href="#cite_ref-optimal_6-0">^</a> <cite id="CITEREFSulaiman_Al-BassamBella_Bose1990" class="citation journal cs1">Sulaiman Al-Bassam; Bella Bose (March 1990). "On Balanced Codes". IEEE Transactions on Information Theory. 36 (2): 406–408. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F18.52490">10.1109/18.52490</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFK._Schouhamer_Immink_and_J._Weber2010" class="citation journal cs1"><a href="Kees_Schouhamer_Immink" title="Kees Schouhamer Immink">K. Schouhamer Immink</a> and J. Weber (2010). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/224110287">"Very efficient balanced codes"</a>. IEEE Journal on Selected Areas in Communications. 28 (2): 188–192. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fjsac.2010.100207">10.1109/jsac.2010.100207</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8596702">8596702</a>. Retrieved 2018-02-12.</cite>

</li>

<a rel="nofollow" class="external text" href="https://www.design-reuse.com/articles/43954/demystifying-mipi-c-phy-dphy-subsystem.html">"Demystifying MIPI C-PHY / DPHY Subsystem - Tradeoffs, Challenges, and Adoption"</a>

(<a rel="nofollow" class="external text" href="https://www.chipestimate.com/Demystifying-MIPI-C-PHY--DPHY-Subsystem-Tradeoffs-Challenges-and-Adoption-/Mixel/Technical-Article/2018/04/24">mirror</a>)

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.win.tue.nl/~aeb/codes/Andw.html">Table of lower bounds on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(n,d,w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(n,d,w)}</annotation>

</semantics>

<li><a rel="nofollow" class="external text" href="http://codes.se/bounds/">Table of upper bounds on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(n,d,w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(n,d,w)}</annotation>

</semantics>

This article is issued from <a class="external text" title="Last edited on 2025-04-07" href="https://en.wikipedia.org/wiki/?title=Constant-weight_code&oldid=1284488701">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>